home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_200 / 244_01 / four31.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-10-24  |  10.9 KB  |  413 lines
  1.  
  2. /* program to analyze the de Bruijn diagram of a cellular */
  3. /* automaton and report all the periodic states. */
  4. /* version for totalistic (3,1), fourth generation */
  5. /* [Harold V. McIntosh, 18 May 1987] */
  6.  
  7. # include <stdio.h>
  8.  
  9. # define MC     6                /* maximum number of columns */
  10. # define NS      7                /* number of distinct sums */
  11. # define ML    24                /* pause after so many lines */
  12.  
  13. char arry[3][3][3][3][3][3][3][3][3];
  14. int  rule[NS];
  15. int  nc, nl;
  16.  
  17. main() {
  18. int i;
  19.  
  20. printf("Rule number:\n");
  21. printf("0..1..2\n");
  22. for (i=0; i<NS; i++) rule[i]=getchar()-'0';
  23.  
  24. nc=0;
  25. nl=0;
  26.  
  27. printf("\n - several minutes may elapse for each case - \n");
  28.  
  29. kwait(0); printf("Strings conforming to (4,0):"); kwait(0);
  30. pass1a();
  31. pass2i();
  32. pass2o();
  33. pass4();
  34.  
  35. kwait(0); printf("Strings conforming to (4,1):"); kwait(0);
  36. pass1b();
  37. pass2i();
  38. pass2o();
  39. pass4();
  40.  
  41. kwait(0); printf("Strings conforming to (4,2):"); kwait(0);
  42. pass1c();
  43. pass2i();
  44. pass2o();
  45. pass4();
  46.  
  47. kwait(0); printf("Strings conforming to (4,3):"); kwait(0);
  48. pass1d();
  49. pass2i();
  50. pass2o();
  51. pass4();
  52.  
  53. kwait(0); printf("Strings conforming to (4,4):"); kwait(0);
  54. pass1e();
  55. pass2i();
  56. pass2o();
  57. pass4();
  58.  
  59. } /* end of main */
  60.  
  61. pass1a() {            /* mark sequences conforming to (4,0) */
  62. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  63. int j0, j1, j2, j3, j4, j5, j6;
  64. int k0, k1, k2, k3, k4;
  65. int i, j, k;
  66. printf(" pass1a\015");
  67. for (i0=0; i0<3; i0++) {
  68. for (i1=0; i1<3; i1++) {
  69. for (i2=0; i2<3; i2++) {
  70. for (i3=0; i3<3; i3++) {
  71. for (i4=0; i4<3; i4++) {
  72. for (i5=0; i5<3; i5++) {
  73. for (i6=0; i6<3; i6++) {
  74. for (i7=0; i7<3; i7++) {
  75. for (i8=0; i8<3; i8++) {
  76. j0=rule[i0+i1+i2];
  77. j1=rule[i1+i2+i3];
  78. j2=rule[i2+i3+i4];
  79. j3=rule[i3+i4+i5];
  80. j4=rule[i4+i5+i6];
  81. j5=rule[i5+i6+i7];
  82. j6=rule[i6+i7+i8];
  83. k0=rule[j0+j1+j2];
  84. k1=rule[j1+j2+j3];
  85. k2=rule[j2+j3+j4];
  86. k3=rule[j3+j4+j5];
  87. k4=rule[j4+j5+j6];
  88. i=rule[k0+k1+k2];
  89. j=rule[k1+k2+k3];
  90. k=rule[k2+k3+k4];
  91. arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]=rule[i+j+k]==i4?'Y':'N';
  92. };};};};};};};};};
  93. }
  94.  
  95. pass1b() {            /* mark sequences conforming to (4,1) */
  96. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  97. int j0, j1, j2, j3, j4, j5, j6;
  98. int k0, k1, k2, k3 ,k4;
  99. int i, j, k;
  100. printf(" pass1a\015");
  101. for (i0=0; i0<3; i0++) {
  102. for (i1=0; i1<3; i1++) {
  103. for (i2=0; i2<3; i2++) {
  104. for (i3=0; i3<3; i3++) {
  105. for (i4=0; i4<3; i4++) {
  106. for (i5=0; i5<3; i5++) {
  107. for (i6=0; i6<3; i6++) {
  108. for (i7=0; i7<3; i7++) {
  109. for (i8=0; i8<3; i8++) {
  110. j0=rule[i0+i1+i2];
  111. j1=rule[i1+i2+i3];
  112. j2=rule[i2+i3+i4];
  113. j3=rule[i3+i4+i5];
  114. j4=rule[i4+i5+i6];
  115. j5=rule[i5+i6+i7];
  116. j6=rule[i6+i7+i8];
  117. k0=rule[j0+j1+j2];
  118. k1=rule[j1+j2+j3];
  119. k2=rule[j2+j3+j4];
  120. k3=rule[j3+j4+j5];
  121. k4=rule[j4+j5+j6];
  122. i=rule[k0+k1+k2];
  123. j=rule[k1+k2+k3];
  124. k=rule[k2+k3+k4];
  125. arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]=rule[i+j+k]==i3?'Y':'N';
  126. };};};};};};};};};
  127. }
  128.  
  129. pass1c() {            /* mark sequences conforming to (4,2) */
  130. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  131. int j0, j1, j2, j3, j4, j5, j6;
  132. int k0, k1, k2, k3 ,k4;
  133. int i, j, k;
  134. printf(" pass1a\015");
  135. for (i0=0; i0<3; i0++) {
  136. for (i1=0; i1<3; i1++) {
  137. for (i2=0; i2<3; i2++) {
  138. for (i3=0; i3<3; i3++) {
  139. for (i4=0; i4<3; i4++) {
  140. for (i5=0; i5<3; i5++) {
  141. for (i6=0; i6<3; i6++) {
  142. for (i7=0; i7<3; i7++) {
  143. for (i8=0; i8<3; i8++) {
  144. j0=rule[i0+i1+i2];
  145. j1=rule[i1+i2+i3];
  146. j2=rule[i2+i3+i4];
  147. j3=rule[i3+i4+i5];
  148. j4=rule[i4+i5+i6];
  149. j5=rule[i5+i6+i7];
  150. j6=rule[i6+i7+i8];
  151. k0=rule[j0+j1+j2];
  152. k1=rule[j1+j2+j3];
  153. k2=rule[j2+j3+j4];
  154. k3=rule[j3+j4+j5];
  155. k4=rule[j4+j5+j6];
  156. i=rule[k0+k1+k2];
  157. j=rule[k1+k2+k3];
  158. k=rule[k2+k3+k4];
  159. arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]=rule[i+j+k]==i2?'Y':'N';
  160. };};};};};};};};};
  161. }
  162.  
  163. pass1d() {            /* mark sequences conforming to (4,3) */
  164. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  165. int j0, j1, j2, j3, j4, j5, j6;
  166. int k0, k1, k2, k3 ,k4;
  167. int i, j, k;
  168. printf(" pass1a\015");
  169. for (i0=0; i0<3; i0++) {
  170. for (i1=0; i1<3; i1++) {
  171. for (i2=0; i2<3; i2++) {
  172. for (i3=0; i3<3; i3++) {
  173. for (i4=0; i4<3; i4++) {
  174. for (i5=0; i5<3; i5++) {
  175. for (i6=0; i6<3; i6++) {
  176. for (i7=0; i7<3; i7++) {
  177. for (i8=0; i8<3; i8++) {
  178. j0=rule[i0+i1+i2];
  179. j1=rule[i1+i2+i3];
  180. j2=rule[i2+i3+i4];
  181. j3=rule[i3+i4+i5];
  182. j4=rule[i4+i5+i6];
  183. j5=rule[i5+i6+i7];
  184. j6=rule[i6+i7+i8];
  185. k0=rule[j0+j1+j2];
  186. k1=rule[j1+j2+j3];
  187. k2=rule[j2+j3+j4];
  188. k3=rule[j3+j4+j5];
  189. k4=rule[j4+j5+j6];
  190. i=rule[k0+k1+k2];
  191. j=rule[k1+k2+k3];
  192. k=rule[k2+k3+k4];
  193. arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]=rule[i+j+k]==i1?'Y':'N';
  194. };};};};};};};};};
  195. }
  196.  
  197. pass1e() {            /* mark sequences conforming to (4,4) */
  198. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  199. int j0, j1, j2, j3, j4, j5, j6;
  200. int k0, k1, k2, k3 ,k4;
  201. int i, j, k;
  202. printf(" pass1a\015");
  203. for (i0=0; i0<3; i0++) {
  204. for (i1=0; i1<3; i1++) {
  205. for (i2=0; i2<3; i2++) {
  206. for (i3=0; i3<3; i3++) {
  207. for (i4=0; i4<3; i4++) {
  208. for (i5=0; i5<3; i5++) {
  209. for (i6=0; i6<3; i6++) {
  210. for (i7=0; i7<3; i7++) {
  211. for (i8=0; i8<3; i8++) {
  212. j0=rule[i0+i1+i2];
  213. j1=rule[i1+i2+i3];
  214. j2=rule[i2+i3+i4];
  215. j3=rule[i3+i4+i5];
  216. j4=rule[i4+i5+i6];
  217. j5=rule[i5+i6+i7];
  218. j6=rule[i6+i7+i8];
  219. k0=rule[j0+j1+j2];
  220. k1=rule[j1+j2+j3];
  221. k2=rule[j2+j3+j4];
  222. k3=rule[j3+j4+j5];
  223. k4=rule[j4+j5+j6];
  224. i=rule[k0+k1+k2];
  225. j=rule[k1+k2+k3];
  226. k=rule[k2+k3+k4];
  227. arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]=rule[i+j+k]==i0?'Y':'N';
  228. };};};};};};};};};
  229. }
  230.  
  231. /* Pass2i flags links which have an incoming arrow */
  232. pass2i() {int i0, i1, i2, i3, i4, i5, i6, i7, i8, m;
  233. do {
  234. printf(" pass2i\015");
  235. for (i0=0; i0<3; i0++) {
  236. for (i1=0; i1<3; i1++) {
  237. for (i2=0; i2<3; i2++) {
  238. for (i3=0; i3<3; i3++) {
  239. for (i4=0; i4<3; i4++) {
  240. for (i5=0; i5<3; i5++) {
  241. for (i6=0; i6<3; i6++) {
  242. for (i7=0; i7<3; i7++) {
  243. for (i8=0; i8<3; i8++) {
  244. if ((arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]&0x5F)=='Y')
  245.  {for (m=0; m<3; m++) arry[i1][i2][i3][i4][i5][i6][i7][i8][m]|=0x20;};
  246. };};};};};};};};};
  247. } while (pass3()!=0); }
  248.  
  249. /* Pass2o flags links which have an outgoing arrow */
  250. pass2o() {int i0, i1, i2, i3, i4, i5, i6, i7, i8, m;
  251. do {
  252. printf(" pass2o\015");
  253. for (i0=0; i0<3; i0++) {
  254. for (i1=0; i1<3; i1++) {
  255. for (i2=0; i2<3; i2++) {
  256. for (i3=0; i3<3; i3++) {
  257. for (i4=0; i4<3; i4++) {
  258. for (i5=0; i5<3; i5++) {
  259. for (i6=0; i6<3; i6++) {
  260. for (i7=0; i7<3; i7++) {
  261. for (i8=0; i8<3; i8++) {
  262. if ((arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]&0x5F)=='Y')
  263.  {for (m=0; m<3; m++) arry[m][i0][i1][i2][i3][i4][i5][i6][i7]|=0x20;};
  264. };};};};};};};};};
  265. } while (pass3()!=0); }
  266.  
  267. /* erase flags, mark survivors, count channges */
  268. int pass3() {int i0, i1, i2, i3, i4, i5, i6, i7, i8, l;
  269. l=0;
  270. printf(" pass3 \015");
  271. for (i0=0; i0<3; i0++) {
  272. for (i1=0; i1<3; i1++) {
  273. for (i2=0; i2<3; i2++) {
  274. for (i3=0; i3<3; i3++) {
  275. for (i4=0; i4<3; i4++) {
  276. for (i5=0; i5<3; i5++) {
  277. for (i6=0; i6<3; i6++) {
  278. for (i7=0; i7<3; i7++) {
  279. for (i8=0; i8<3; i8++) {
  280. switch (arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]) {
  281.     case 'y': arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]='Y'; break;
  282.     case 'Y': arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]='N'; l=1; break;
  283.     case 'n': case 'N': arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]='N'; break;
  284.     default: break; };
  285. };};};};};};};};};
  286. return l; }
  287.  
  288. /* pass4 - print loops which remain */
  289. pass4() {
  290. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  291. int j0, j1, j2, j3, j4, j5, j6, j7, j8;
  292. int k, l, m;
  293. printf(" pass4 \015");
  294. for (i0=0; i0<3; i0++) {
  295. for (i1=0; i1<3; i1++) {
  296. for (i2=0; i2<3; i2++) {
  297. for (i3=0; i3<3; i3++) {
  298. for (i4=0; i4<3; i4++) {
  299. for (i5=0; i5<3; i5++) {
  300. for (i6=0; i6<3; i6++) {
  301. for (i7=0; i7<3; i7++) {
  302. for (i8=0; i8<3; i8++) {
  303. j1=i1; j2=i2; j3=i3; j4=i4; j5=i5; j6=i6; j7=i7; j8=i8;
  304. l=0;
  305. m=0;
  306. do {
  307.         if (arry[0][j1][j2][j3][j4][j5][j6][j7][j8]=='Y')
  308.     {arry[0][j1][j2][j3][j4][j5][j6][j7][j8]='y';
  309.     k=j8; j8=j7; j7=j6; j6=j5; j5=j4; j4=j3; j3=j2; j2=j1; j1=0; m=1;}
  310.   else {if (arry[1][j1][j2][j3][j4][j5][j6][j7][j8]=='Y')
  311.     {arry[1][j1][j2][j3][j4][j5][j6][j7][j8]='y';
  312.     k=j8; j8=j7; j7=j6; j6=j5; j5=j4; j4=j3; j3=j2; j2=j1; j1=1; m=1;}
  313.   else {if (arry[2][j1][j2][j3][j4][j5][j6][j7][j8]=='Y')
  314.     {arry[2][j1][j2][j3][j4][j5][j6][j7][j8]='y';
  315.     k=j8; j8=j7; j7=j6; j6=j5; j5=j4; j4=j3; j3=j2; j2=j1; j1=2; m=1;}
  316.   else {l=1;
  317.     if (m==1) {j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=j8; j8=k;};
  318.     };};};
  319.   } while (l==0);
  320. l=0; 
  321. m=0;
  322. do {
  323.         if (arry[j0][j1][j2][j3][j4][j5][j6][j7][0]=='y')
  324.    {prf(j0,j1,j2,j3,j4,j5,j6,j7,0);
  325.    arry[j0][j1][j2][j3][j4][j5][j6][j7][0]='N';
  326.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=0; m=1;}
  327.   else {if (arry[j0][j1][j2][j3][j4][j5][j6][j7][1]=='y')
  328.    {prf(j0,j1,j2,j3,j4,j5,j6,j7,1);
  329.    arry[j0][j1][j2][j3][j4][j5][j6][j7][1]='N';
  330.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=1; m=1;}
  331.   else {if (arry[j0][j1][j2][j3][j4][j5][j6][j7][2]=='y')
  332.    {prf(j0,j1,j2,j3,j4,j5,j6,j7,2);
  333.    arry[j0][j1][j2][j3][j4][j5][j6][j7][2]='N';
  334.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=2; m=1;}
  335.   else {l=1;};};};
  336.   } while (l==0);
  337. l=0;
  338. do {
  339.         if (arry[j0][j1][j2][j3][j4][j5][j6][j7][0]=='Y')
  340.    {prf(j0,j1,j2,j3,j4,j5,j6,j7,0);
  341.    arry[j0][j1][j2][j3][j4][j5][j6][j7][0]='N';
  342.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=0; m=1;}
  343.   else {if (arry[j0][j1][j2][j3][j4][j5][j6][j7][1]=='Y')
  344.    {prf(j0,j1,j2,j3,j4,j5,j6,j7,1);
  345.    arry[j0][j1][j2][j3][j4][j5][j6][j7][1]='N';
  346.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=1; m=1;}
  347.   else {if (arry[j0][j1][j2][j3][j4][j5][j6][j7][2]=='Y')
  348.    {prf(j0,j1,j2,j3,j4,j5,j6,j7,2);
  349.    arry[j0][j1][j2][j3][j4][j5][j6][j7][2]='N';
  350.    j0=j1; j1=j2; j2=j3; j3=j4; j4=j5; j5=j6; j6=j7; j7=2; m=1;}
  351.   else {l=1; if (m==1) kwait(0);};};};
  352.   } while (l==0);
  353. };};};};};};};};};
  354. }
  355.  
  356. /* print one of the individual links in a chain */
  357. prf(i0,i1,i2,i3,i4,i5,i6,i7,i8)
  358. int i0, i1, i2, i3, i4, i5, i6, i7, i8; {
  359. kwait(1);
  360. printf("%1d",i0);
  361. printf("%1d",i1);
  362. printf("%1d",i2);
  363. printf("%1d",i3);
  364. printf("%1d",i4);
  365. printf("%1d",i5);
  366. printf("%1d",i6);
  367. printf("%1d",i7);
  368. printf("-");
  369. printf("%1d",i8);
  370. printf(" ");}
  371.  
  372. /* print the whole list of links - impractical except for debugging  */
  373. pall() {
  374. int i0, i1, i2, i3, i4, i5, i6, i7, i8;
  375. for (i0=0; i0<3; i0++) {
  376. for (i1=0; i1<3; i1++) {
  377. for (i2=0; i2<3; i2++) {
  378. for (i3=0; i3<3; i3++) {
  379. for (i4=0; i4<3; i4++) {
  380. for (i5=0; i5<3; i5++) {
  381. for (i6=0; i6<3; i6++) {
  382. for (i7=0; i7<3; i7++) {
  383. for (i8=0; i8<3; i8++) {
  384. printf("%c",arry[i0][i1][i2][i3][i4][i5][i6][i7][i8]);
  385. };};};};};};};};};
  386. printf("\n");
  387. }
  388.  
  389. /* keyboard status */
  390. kbdst() {return bdos(11)&0xFF;}
  391.  
  392. /* direct keyboard input, no echo */
  393. kbdin() {int c;
  394. if ((c=bdos(7)&0xFF)=='\0') c=(bdos(7)&0xFF)|0x80;
  395. return c;}
  396.  
  397. /* pause at the end of a full screen */
  398. kwait(i) int i; {
  399. switch (i) {
  400.   case 0: printf("\n"); nc=0; nl++; break;
  401.   case 1: {if (nc==MC) {printf("&\n"); nc=1; nl++;} else nc++;}; break;
  402.   default: break;};
  403. if (nl==ML) {
  404.   nl=0;
  405.   printf(" press any key to continue\015");
  406.   while (kbdst()) {};
  407.   kbdin();
  408.   printf("-                         \n");
  409.   };
  410. }
  411.  
  412. /* end */
  413.